package 值和下标之差都在给定的范围内;

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Solution main = new Solution();
        int[] nums = new int[] {      1,5,9,1,5,9    };
//        int[] nums = new int[] {        1,2,3,1     };
        System.out.println(main.containsNearbyAlmostDuplicate(nums,2,3));
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t)
    {
        int n = nums.length;

        TreeSet<Long> ts = new TreeSet<>();

        int r = 0;
        while (r < n)
        {
            Long ge = ts.floor((long)nums[r]);
            if (ge != null && Math.abs(nums[r] - ge) <= t)
                return true;
            Long le = ts.ceiling((long)nums[r]);
            if (le != null && Math.abs(nums[r] - le) <= t)
                return true;

            ts.add((long)nums[r]);

            if (k <= r)
            {
                int l = r - k;
                ts.remove((long)nums[l]);
            }

            r ++;
        }

        return false;
    }


}
